package com.yxp.offer;

/**
 * @author : yang.xp
 * @date : 2021/8/16 9:32
 * @description : 剑指 Offer 53 - I. 在排序数组中查找数字 I
 */
public class Problem53_1 {

    public static void main(String[] args) {
        int[] numbers = new int[]{5, 7, 7, 8, 8, 10};
        System.out.println(search(numbers, 6));
        System.out.println(searchBin(numbers, 7));
    }

    /**
     * 顺序查找到第一个，然后往后计数
     *
     * @param numbers
     * @param target
     * @return
     */
    public static int search(int[] numbers, int target) {
        if (numbers == null) {
            return 0;
        }
        int firstIndex = 0;
        while (firstIndex < numbers.length) {
            if (numbers[firstIndex] == target) {
                break;
            }
            firstIndex++;
        }
        int i = firstIndex;
        while (firstIndex < numbers.length) {
            if (numbers[firstIndex++] != target) {
                firstIndex -= 1;
                break;
            }
        }
        return firstIndex - i;
    }

    /**
     * 二分查找到第n个，然后两边查找。
     *
     * @return
     */
    public static int searchBin(int[] numbers, int target) {
        int searchbb = searchbb(numbers, target, 0, numbers.length);
        if (searchbb == -1) {
            return 0;
        }
        int begin = searchbb;
        int end = searchbb;
        while (begin > 0) {
            if (numbers[--begin] != target) {
                begin += 1;
                break;
            }
        }
        while (end < numbers.length) {
            if (numbers[++end] != target) {
                end -= 1;
                break;
            }
        }

        return end - begin;
    }

    public static int searchbb(int[] numbers, int target, int begin, int end) {
        int mid = (begin + end) / 2;
        if (begin > end) {
            return -1;
        }
        if (numbers[mid] == target) {
            return mid;
        }
        if (numbers[mid] < target) {
            return searchbb(numbers, target, mid + 1, end);
        }
        if (numbers[mid] > target) {
            return searchbb(numbers, target, begin, mid - 1);
        }
        return -1;
    }
}
